UVa/10199 - Tourist guide/10199.cpp

   1 #include <vector>
   2 #include <set>
   3 #include <map>
   4 #include <algorithm>
   5 #include <iostream>
   6 #include <iterator>
   7
   8 using namespace std;
   9
  10 typedef string node;
  11 typedef map<node, vector<node> > graph;
  12 typedef char color;
  13
  14 const color WHITE = 0, GRAY = 1, BLACK = 2;
  15
  16 graph g;
  17 map<node, color> colors;
  18
  19 set<node> dfs(node v, set<node> visited, const node& ignore){
  20   colors[v] = GRAY;
  21   vector<node> neighbors = g[v];
  22   visited.insert(v);
  23   for (int i=0; i<neighbors.size(); ++i){
  24     if (visited.count(neighbors[i]) == 0 && neighbors[i] != ignore){
  25       set<node> temp = dfs(neighbors[i], visited, ignore);
  26
  27       for (set<node>::iterator j = temp.begin(); j != temp.end(); ++j){
  28         visited.insert(*j);
  29       }
  30
  31     }
  32   }
  33   colors[v] = BLACK;
  34   return visited;
  35 }
  36
  37 int main(){
  38   int n;
  39   int map = 1;
  40   while (cin >> n && n > 0){
  41     if (map > 1) cout << endl;
  42     g.clear();
  43     colors.clear();
  44     while (n--){
  45       node v;
  46       cin >> v;
  47       colors[v] = WHITE;
  48       g[v] = vector<node>();
  49     }
  50
  51     cin >> n;
  52     while (n--){
  53       node v,u;
  54       cin >> v >> u;
  55       g[v].push_back(u);
  56       g[u].push_back(v);
  57     }
  58
  59     vector<node> cameras;
  60
  61     for (graph::iterator i = g.begin(); i != g.end(); ++i){
  62       if (colors[(*i).first] == WHITE){
  63         set<node> full;
  64         full = dfs((*i).first, full, "");
  65         if (full.size() == 1) continue;
  66         for (set<node>::iterator j = full.begin(); j != full.end(); ++j){
  67           set<node>::iterator initial = full.begin();
  68           while ((*j) == (*initial)) ++initial;
  69           set<node> temp = dfs((*initial), set<node>(), (*j));
  70           if (temp.size() + 1 < full.size()){ //El +1 es por el nodo que ignoré
  71             cameras.push_back(*j);
  72           }
  73         }
  74       }
  75     }
  76
  77
  78     sort(cameras.begin(), cameras.end());
  79     cout << "City map #"<<map<<": " << cameras.size() << " camera(s) found" << endl;
  80     copy(cameras.begin(), cameras.end(), ostream_iterator<node>(cout,"\n"));
  81
  82     ++map;
  83   }
  84   return 0;
  85 }